1. Field of the Invention
This invention relates generally to a method of switching data packets over a multistage interconnection network (MIN). More particularly, this invention relates to a method of switching data packets over the MIN with distributed control. Such method ensures that heavy traffic to one or a set of destinations (hot spot traffic) can be supported with little degradation to the uniform traffic directed to other destinations of the network. Each of the address bits in each packet determines the route of the packet at a particular stage of the network and packets are at a stage of the buffer of criteria of the address bits of packets currently in the buffer, and on the availability of the buffer.
2. Description of Prior Art
As the requirements for computing power grow, the interconnection of a plurality of processors to support the computing requirements becomes increasingly important. Thus, there is a need for a high-speed network for connecting processors to processors, or processors to a shared memory.
Many networks for interconnecting processors to memories are known. Of these networks, MINs are particularly attractive since they provide high bandwidth, can be modularly increased in size by adding stages to the network, and have O(N log N) complexity where N is the number of processors or memory modules. Most importantly, MINs can be controlled using a distributed algorithm without the bottleneck that occurs in networks having a centralized controller.
A serious problem which occurs when MINs are used for processor memory interconnection is tree saturation. This problem is described in Pfister, "Hot Spot Contention and Combining in Multistage Interconnection Networks," IEEE Transactions on Computers, C-34(10) October 1985, pp. 943-948. When the traffic of data packets is transmitted uniformly to the various memory units within the network, this problem does not occur. However, when there is heavy traffic from the processors to a specific memory, called a hot spot, buffers leading to the hot spot fill with packets addressed to the hot spot. These full buffers block traffic from processors to other memories thus bringing the entire network to a halt.
In Pfister, a method called combining is disclosed to alleviate tree saturation. However, non-combinable, non-uniform data access patterns can occur due to (1) particular array access patterns, (2) non-combinable updates to a hot spot, or (3) transient heavy-load to a memory unit rather than to a specific data item. Furthermore, combining may not be feasible for use in a system without shared memory.
MINs have been proposed for telecommunications packet switching. See for example, Turner, U.S. Pat. No. 4,494,230, as well as U.S. Pat. No. 4,491,945 which teach the use of MINs for telecommunication packet switching. Nonuniformities in traffic in such networks produce similar choking of these networks when tree saturation occurs due to heavy non-uniform traffic of packets to a destination in the network. Combining does not work in this application either.
Akashi, U.S. Pat. No. 4,500,990, describes how a buffer overflow signal can be generated in a CSMA/CD network, causing a packet to be retransmitted to a full buffer. This method is specific to the CSMA/CD (Ethernet type) local area network and is not useful in MINs.
Servel, U.S. Pat. No. 4,603,416, describes a switching method in which packets arriving on input links in bit serial fashion are converted to packet parallel form, time slot interchanged in this parallel form, and finally reconverted to bit serial form. Internally, one packet is transmitted at a time, in 128 bit parallel form. The switch is organized as a single stage. The memory is similar to a time slot interchanger and packets are stored in memory modules as they arrive. The packets are then read out from memory at the correct time to feed them to the output lines. This switching method is not useful for solving hot spot problems in MINs.
Chan, U.S. Pat. No. 4,556,972, teaches an interface of a packet switch to a circuit switch in which the number of links allocated to a destination, from the packet switch through the circuit switch, is dynamically controlled and is based on the volume of packet traffic to that destination. A method for monitoring the delay of packets through a packet switch is described in Turner, U.S. Pat. No. 4,551,833.
And finally a method for providing synchronization between a host computer system and several device controllers is taught in Rubinson, U.S. Pat. No. 4,449,182. Each processor operates at its own speed without creating race conditions and eliminates the need for hardware interlock capability on the I/O bus.